#include <stdio.h>
#include <stdlib.h>
#include "BST.h"

void InitBSTree(BST *bst)
{
        bst->root = NULL;
}

int InsertBSTree(BSTNode **t, datatype *x)
{
        BSTNode *current = *t;

        if (current == NULL)
        {
                current = malloc(sizeof(BSTNode));
                current->data = *x;
                current->leftchild = NULL;
                current->rightchild = NULL;
                *t = current;
                return 0;
        }
        else if (current->data > *x)
                InsertBSTree(&(*t)->leftchild, x);
        else if (current->data < *x)
                InsertBSTree(&(*t)->rightchild, x);
        else
                return -1; //二叉排序树中不允许有重复的关键字

        return 0;
}

BSTNode *Min(BSTNode *node)
{
        if (node == NULL)
                return NULL;
        while (node->leftchild != NULL)
                node = node->leftchild;
        return node;
}

BSTNode *Max(BSTNode *node)
{
        if (node == NULL)
                return NULL;
        while (node->rightchild != NULL)
                node = node->rightchild;
        return node;
}

void Sort(BSTNode *node)
{
        if (node == NULL)
                return;
        Sort(node->leftchild);
        printf("%d ", node->data);
        Sort(node->rightchild);
}

int RemoveBSTree(BSTNode **nodep, datatype *key)
{
        BSTNode *current = *nodep;

        if (current == NULL)
                return -1;
        if (*key < current->data)
                RemoveBSTree(&current->leftchild, key);
        else if (*key > current->data)
                RemoveBSTree(&current->rightchild, key);
        else
        {
                if (current->leftchild != NULL && current->rightchild != NULL)
                {
                        current = current->rightchild;
                        while (current->leftchild != NULL)
                                current = current->leftchild;
                        (*nodep)->data = current->data;
                        RemoveBSTree(&(*nodep)->rightchild, &current->data);
                }
                else
                {
                        current = *nodep;
                        if ((*nodep)->leftchild == NULL) //左子树为空则指向右子树
                                (*nodep) = (*nodep)->rightchild;
                        else //右子树为空则指向左子树
                                (*nodep) = (*nodep)->rightchild;
                        free(current);
                }
        }
        return 0;
}

BSTNode *SearchBSTree(BSTNode *node, datatype *key)
{
        if (node == NULL)
                return NULL;
        if (node->data == *key)
                return node;
        else if (node->data > *key)
                return SearchBSTree(node->leftchild, key);
        else
                return SearchBSTree(node->rightchild, key);
}

BSTNode *SearchBSTree2(BSTNode *node, datatype *key)
{
        while (node != NULL && node->data != *key) // node为空或找到结点结束循环
                if (node->data < *key)             //待查找元素值大于根结点值，到右子树中查找
                        node = node->rightchild;
                else
                        node = node->leftchild; //待查找元素值小于根结点值，到左子树中查找

        return node;
}

void MakeEmptyBSTree(BSTNode **nodep)
{
        if (*nodep != NULL)
        {
                MakeEmptyBSTree(&(*nodep)->leftchild);
                MakeEmptyBSTree(&(*nodep)->rightchild);
        }
        free(*nodep);
        *nodep = NULL;
}